package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 143. 重排链表 中档题
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * <p>
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * <p>
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * <p>
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 * <p>
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 *
 * @author zjj_admin
 * @date 2022/11/18 11:50
 */
public class ReorderList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(9, null);
        ListNode node2 = new ListNode(8, node1);
        ListNode node3 = new ListNode(7, node2);
        ListNode node4 = new ListNode(6, node3);
        ListNode node5 = new ListNode(5, node4);
        ListNode node6 = new ListNode(4, null);
        ListNode node7 = new ListNode(3, node6);
        ListNode node8 = new ListNode(2, node7);
        ListNode node9 = new ListNode(1, node8);

        reorderList(node9);

    }



    /**
     * 输入：head = [1,2,3,4]
     * 输出：[1,4,2,3]
     * 思路：
     * 1、获取中间节点
     * 2、将中间节点以后的所有的节点全部逆序
     * 3、将逆序后的后半部分链表没隔一个插入到链表的前半部分
     *
     * @param head
     */
    public static void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        ListNode middle = head;
        ListNode middlePre = new ListNode();
        middlePre.next = middle;
        ListNode curr = head;
        boolean doubled = false;
        //两个节点依次向后面遍历，curr 节点每走两步，resNode 节点就走一步
        //当curr 节点到了最末尾时，redNode 节点就指向了中间节点
        while (curr != null) {
            if (doubled) {
                middlePre = middlePre.next;
                middle = middle.next;
            }
            doubled = !doubled;
            curr = curr.next;
        }
        middlePre.next = null;
        //将链表从 middlePre 的位置砍断
        //此时middle就是后面部分的头结点，这个时候需要将 middle 为头结点的链表逆序
        ListNode newHead = reverse(middle);
        //将两个链表合并
//        merge(head, newHead);
        while (newHead != null) {
            //定义一个伪节点，存储第二个链表的第二节点
            ListNode temp = newHead.next;
            //将第二个链表的头节点，指向第一个链表链表的第二个节点。
            newHead.next = head.next;
            //将第一个链表的头节点，指向第二个链表的头节点。
            head.next = newHead;
            //将指向第一个链表的头节点的指针，移动到第一个链表的第二个节点
            head = newHead.next;
            //将指向第二个链表的头节点的指针，移动到第二个链表的第二个节点
            newHead = temp;
        }

    }

    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            //将当前节点的下一个节点指向prev
            cur.next = prev;
            prev = cur;
            //将当前指针向后移动
            cur = next;
        }
        return prev;
    }

    /**
     * 合并两个链表
     *
     * @param l1
     * @param l2
     */
    private static void merge(ListNode l1, ListNode l2) {
        ListNode tem1, tem2;
//        while (l1 != null && l2 != null) {
//            tem1 = l1.next;
//            tem2 = l2.next;
//            l1.next = l2;
//            l1 = tem1;
//            l2.next = l1;
//            l2 = tem2;
//        }

        ListNode curr1,curr2;
        curr1 = l1;
        curr2 = l2;
        while (curr2 != null){
            ListNode temp = curr2;

            temp.next = curr1.next;
            curr1.next = temp;

            curr2 = curr2.next;
            curr1 = curr1.next;
            if(curr1.next != null){
                curr1 = curr1.next;
            }
        }

        System.out.println("ss");
    }


}
